<?php
/*
 * 把一棵搜索二叉树，转化成有序的双向链表
 */

require_once '../../../class/DoubleListNode.class.php';

$head                     = new DoubleListNode(5);
$head->left               = new DoubleListNode(2);
$head->right              = new DoubleListNode(9);
$head->left->left         = new DoubleListNode(1);
$head->left->right        = new DoubleListNode(3);
$head->left->right->right = new DoubleListNode(4);
$head->right->left        = new DoubleListNode(7);
$head->right->right       = new DoubleListNode(10);
$head->left->left         = new DoubleListNode(1);
$head->right->left->left  = new DoubleListNode(6);
$head->right->left->right = new DoubleListNode(8);

$obj = new Code_04_BST2DoubleLinkedList();
$obj->printBSTInOrder($head);
$node = $obj->do($head);

class Code_04_BST2DoubleLinkedList
{
    public $queue;

    public function printBSTInOrder($head)
    {
        echo "BST in-order: ";
        if ($head != null) {
            $this->inOrderPrint($head);
        }
        echo PHP_EOL;
    }

    public function inOrderPrint($head) {
		if ($head == null) {
			return;
		}
        $this->inOrderPrint($head->left);
        echo $head->val .' ';
		$this->inOrderPrint($head->right);
	}

    public function do($head)
    {
        $this->queue = new SplQueue();
        $this->inOrderToQueue($head);
        if ($this->queue->isEmpty()) {
            return $head;
        }
        $head      = $this->queue->dequeue();
        $pre       = $head;
        $pre->left = null;
        while (!$this->queue->isEmpty()) {
            $cur        = $this->queue->dequeue();
            $pre->right = $cur;
            $cur->left  = $pre;
            $pre        = $cur;
        }
        $pre->right = null;

        $this->printDoubleLinkedList($head);
//        return $head;
    }

    public function inOrderToQueue($head)
    {
        if ($head == null) {
            return;
        }
        $this->inOrderToQueue($head->left);
        $this->queue->enqueue($head);
        $this->inOrderToQueue($head->right);
    }

    public function printDoubleLinkedList($head) {
		echo "Double Linked List: ";
		$end = null;
		while ($head != null) {
			echo $head->val . " ";
			$end = $head;
			$head = $head->right;
		}
        echo "| ";
		while ($end != null) {
            echo $end->val. " ";
			$end = $end->left;
		}
		echo PHP_EOL;
	}

}